<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>BinarySearchTree</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }
      }
      class BinarySearchTree {
        constructor() {
          this.root = null;
        }
        // 插入新的键
        insert(key) {
          let newNode = new Node(key);
          if (this.root == null) {
            this.root = newNode;
          } else {
            BinarySearchTree.insertNode(newNode, this.root);
          }
        }
        // 查找键
        search(key) {
          // let node = this.root;
          // while (node != null) {
          //   if (key > node.key) {
          //     node = node.right;
          //   } else if (key < node.key) {
          //     node = node.left;
          //   } else {
          //     return node;
          //   }
          // }
          // return null;
          return BinarySearchTree.serachNode(key, this.root);
        }
        // 中序遍历
        inOrderTraverse(handler) {
          BinarySearchTree.inOrderTraverseNode(this.root, handler);
        }
        // 先序遍历
        preOrderTraverse(handler) {
          BinarySearchTree.preOrderTraverseNode(this.root, handler);
        }
        // 后序遍历
        postOrderTraverse(handler) {
          BinarySearchTree.postOrderTraverseNode(this.root, handler);
        }
        // 最小值
        min() {
          let node = this.root,
            key = null;
          while (node != null) {
            key = node.key;
            node = node.left;
          }
          return key;
        }
        // 最大值
        max() {
          let node = this.root,
            key = null;
          while (node != null) {
            key = node.key;
            node = node.right;
          }
          return key;
        }
        // 删除键
        remove(key) {
          let current = this.root,
            parent = null,
            isLeftChild = true;
          while (current.key != key) {
            parent = current;
            if (key < current.key) {
              isLeftChild = true;
              current = current.left;
            } else {
              isLeftChild = false;
              current = current.right;
            }
            // 找到最后 没有找到
            if (current == null) return false;
          }
          // 1 叶子节点
          if (current.left == null && current.right == null) {
            // 根节点 切是叶子节点
            if (current == this.root) {
              this.root = null;
            } // 左
            else if (isLeftChild) {
              parent.left = null;
            } // 右
            else {
              parent.right = null;
            }
          }
          // 2 一个子节点
          else if (current.left == null) {
            if (current == this.root) {
              this.root = current.left;
            } else if (isLeftChild) {
              parent.left = current.left;
            } else {
              parent.right = current.left;
            }
          } else if (current.right == null) {
            if (current == this.root) {
              this.root = current.right;
            } else if (isLeftChild) {
              parent.left = current.right;
            } else {
              parent.right = current.right;
            }
          }
          // 3 二个子节点
          else {
            // 后继方法删除
            // let successor = BinarySearchTree.successorNode(current);
            // if (current == this.root) {
            //   this.root = successor;
            // } else if (isLeftChild) {
            //   parent.left = successor;
            // } else {
            //   parent.right = successor;
            // }
            // successor.left = current.left;
            // 前驱方法删除
            let predecessor = BinarySearchTree.predecessorNode(current);
            if (current == this.root) {
              this.root = predecessor;
            } else if (isLeftChild) {
              parent.left = predecessor;
            } else {
              parent.right = predecessor;
            }
            predecessor.right = current.right;
          }
        }
        static insertNode(newNode, node) {
          if (newNode.key < node.key) {
            if (node.left == null) {
              node.left = newNode;
            } else {
              BinarySearchTree.insertNode(newNode, node.left);
            }
          } else {
            if (node.right == null) {
              node.right = newNode;
            } else {
              BinarySearchTree.insertNode(newNode, node.right);
            }
          }
        }
        static preOrderTraverseNode(node, handler) {
          if (node != null) {
            handler(node.key);
            BinarySearchTree.preOrderTraverseNode(node.left, handler);
            BinarySearchTree.preOrderTraverseNode(node.right, handler);
          }
        }
        static inOrderTraverseNode(node, handler) {
          if (node != null) {
            BinarySearchTree.inOrderTraverseNode(node.left, handler);
            handler(node.key);
            BinarySearchTree.inOrderTraverseNode(node.right, handler);
          }
        }
        static postOrderTraverseNode(node, handler) {
          if (node != null) {
            BinarySearchTree.postOrderTraverseNode(node.left, handler);
            BinarySearchTree.postOrderTraverseNode(node.right, handler);
            handler(node.key);
          }
        }
        static serachNode(key, node) {
          if (key > node.key) {
            node = node.right;
          } else if (key < node.key) {
            node = node.left;
          } else {
            return node;
          }
          return BinarySearchTree.serachNode(key, node);
        }
        // 前驱
        static predecessorNode(node) {
          let predecessor = node,
            current = node.left,
            predecessorParent = null;
          while (current != null) {
            predecessorParent = predecessor;
            predecessor = current;
            current = current.right;
          }
          if (predecessor != node.left) {
            predecessorParent.right = predecessor.left;
            predecessor.left = node.left;
          }
          return predecessor;
        }
        // 后继
        static successorNode(node) {
          let successor = node,
            current = node.right,
            successorParent = null;
          while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
          }
          if (successor != node.right) {
            successorParent.left = successor.right;
            successor.right = node.right;
          }
          return successor;
        }
      }

      let tree = new BinarySearchTree();
      let arr = [11,9,18,7,10,12,19,3,8];
      for (let i = 0; i < arr.length; i++) {
        tree.insert(arr[i]);
      }
      // console.log(tree);
      let str1 = "";
      let str2 = "";
      let str3 = "";
      tree.preOrderTraverse(function (key) {
        str1 += key + " ";
      });
      tree.inOrderTraverse(function (key) {
        str2 += key + " ";
      });
      tree.postOrderTraverse(function (key) {
        str3 += key + " ";
      });
      // console.log(str1);
      // console.log(str2);
      // console.log(str3);
      // console.log(tree.min());
      // console.log(tree.max());
      // tree.search(10);
      // tree.search(10);
      // console.log(tree.search(1));
      tree.remove(7);
      console.log(tree);
    </script>
  </body>
</html>
